// 万能头文件（缺点：包了很多头文件导致编译非常慢）
// #include <bits/stdc++.h>

#include <iostream>
#include <algorithm>
#include <list>
#include <vector>

using namespace std;

template <typename Container, typename T>
void Remove(Container &v, const T &value)
{
    for (auto ite = v.begin(); ite != v.end();)
    {
        if (*ite == 3)
            ite = v.erase(ite);
        else
            ite++;
    }
}

// 洗牌算法
template <typename Iterator>
void RandomShuffle(Iterator start, Iterator end)
{
    if (start == end)
        return;
    for (auto i = start + 1; i != end; i++)
    {
        // 核心思想
        auto j = start + std::rand() % (i - start + 1);
        if (i != j)
            swap(*i, *j);
    }
}

int main()
{
// 1、非变动性算法（传的是值）
#if 0
    // for_each() 对其中每个元素执行某操作
    vector<int> v = {1, 2, 3, 4, 5};

    for_each(v.begin(), v.end(), [](int a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    // count() 返回元素个数（找相等）
    // count()_if() 返回满足某一条件的元素个数
    vector<int> v = {1, 2, 3, 2, 4, 5};

    // 统计出符合条件的数有多少个
    cout << count(v.begin(), v.end(), 2) << endl; // 统计某个值的出现次数
    cout << count_if(v.begin(), v.end(), [](int a)
                     { return a % 2 != 0; })
         << endl; // 可以根据任意条件统计满足条件的元素个数
#endif

#if 0
    // min_element() 返回最小值元素
    // max_element() 返回最大值元素
    vector<int> v = {1, 2, 3, 2, 4, 5};

    // 返回值是个迭代器，所以取它的值得用*
    cout << *min_element(v.begin(), v.end()) << endl;
    cout << *max_element(v.begin(), v.end()) << endl;
#endif

#if 0
    // find() 搜索等于某个值的第一个元素
    // find_if() 搜索满足某个条件的第一个元素
    vector<int> v = {1, 2, 3, 2, 4, 5};

    auto ite = find(v.begin(), v.end(), 2);
    auto ite2 = find_if(v.begin(), v.end(), [](int a)
                        { return a % 2 != 0 && a > 3; });
    // 找不到就返回end迭代器
    if (ite != v.end())
    {
        cout << *ite << endl;
    }

    if (ite2 != v.end())
    {
        cout << *ite2 << endl;
    }
#endif

#if 0
    // search_n() 搜索具有某特性的第一段n个连续元素
    vector<int> v = {1, 2, 2, 3, 3, 5};

    auto ite = search_n(v.begin(), v.end(), 2, 3); // 找两个连续的3
    cout << *ite << endl;
#endif

#if 0
    // search() 搜索某个子区间第一次出现位置
    vector<int> v = {1, 4, 3, 3, 2, 4, 5};
    vector<int> v2 = {4, 3, 3};

    // 在前一个区间找后一个区间，返回找到的在第一个区间的迭代器
    auto ite = search(v.begin(), v.end(), v2.begin(), v2.end());
    cout << *ite << endl;
#endif

#if 0
    // find_end() 搜索某个子区间最后一次出现位置
    vector<int> v = {2, 3, 3, 2, 3, 3, 5};
    vector<int> v2 = {2, 3, 3};

    auto ite = find_end(v.begin(), v.end(), v2.begin(), v2.end());
    cout << *ite << endl;
#endif

#if 0
    // find_first_of() 搜索等于“某数个值之一”的第一元素
    vector<int> v = {1, 2, 3, 3, 3, 4, 5};
    vector<int> v2 = {5, 3, 2};

    // 在第一个区间中找第二个区间中第一次出现的元素
    auto ite = find_first_of(v.begin(), v.end(), v2.begin(), v2.end());
    cout << *ite << endl;
#endif

#if 0
    // adjacent_find() 搜索连续两个相等的元素
    vector<int> v = {1, 2, 5, 5, 3, 4, 5};

    auto ite = adjacent_find(v.begin(), v.end());
    cout << *ite << endl;
#endif

#if 0
    // equal() 判断两区间是否相等
    vector<int> v = {5, 3, 2};
    vector<int> v2 = {5, 3, 2};

    cout << equal(v.begin(), v.end(), v2.begin(), v2.end()) << endl;
#endif

#if 0
    // mismatch()返回两个序列的各组对应元素中，第一对不相等元素
    // vector<int> v = {5, 3, 2};
    // vector<int> v2 = {5, 4, 2};

    // 返回出现的第一对不相等的数
    // auto pair = mismatch(v.begin(), v.end(), v2.begin(), v2.end());

    string s1 = "hello";
    string s2 = "pello";

    // 返回值是一个对组，也可以叫键值对
    // 对于第一个不相等的位置，返回它们的迭代器
    auto pair = mismatch(s1.begin(), s1.end(), s2.begin(), s2.end());
    cout << *pair.first << " " << *pair.second << endl;
#endif

// 2、变动性算法（传的是引用）
// 所有的变动性算法操作一定要先留足空间，也就是先扩容
#if 0
    // for_each() 对每个元素执行某操作
    vector<int> v = {1, 2, 3, 3, 3, 4, 5};
    for_each(v.begin(), v.end(), [](int &a)
             {a++; cout << a << " "; });
    cout << endl;
#endif

#if 1
    // copy() 从第一个元素开始，复制某段区间
    vector<int> v = {1, 2, 3, 3, 3, 4, 5};
    list<int> l;

    // 一定要先扩容
    l.resize(v.size());

    copy(v.begin(), v.end(), l.begin());

    for_each(l.begin(), l.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
    // 可以看出，算法本身对容器是什么类型不关心，所有的容器去适配迭代器，而算法只工作于迭代器（哪怕容器完全不一样也可以拷过去）
    // 这就是迭代器的好处，我们引入迭代器，将容器和算法解耦，相同的算法可以作用于不同的函数
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    copy_backward(v.begin(), v.end(), l.end());

    for_each(l.begin(), l.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    transform(v.begin(), v.end(), l.begin(), [](int a)
              { return a * 2; });

    for_each(l.begin(), l.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    transform(v.begin(), v.end(), l.begin(), [](int a)
              { return a * 2; });

    vector<int> v2;
    v2.resize(v.size() + l.size());
    merge(v.begin(), v.end(), l.begin(), l.end(), v2.begin());

    for_each(v2.begin(), v2.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    transform(v.begin(), v.end(), l.begin(), [](int a)
              { return a * 2; });

    swap_ranges(v.begin(), v.end(), l.begin());
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    transform(v.begin(), v.end(), l.begin(), [](int a)
              { return a * 2; });

    // 数组用fill
    fill(v.begin(), v.end(), 0);
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    transform(v.begin(), v.end(), l.begin(), [](int a)
              { return a * 2; });

    // 链表用fill_n
    fill_n(v.begin(), 3, 0);
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l;
    // 一定要先扩容
    l.resize(v.size());

    transform(v.begin(), v.end(), l.begin(), [](int a)
              { return a * 2; });

    int a = 0;
    // 数组用generate，链表用generate_n
    generate(v.begin(), v.end(), [&a]()
             { return ++a; });
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 1, 2, 3, 4, 5};
    replace(v.begin(), v.end(), 1, 99);

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 1, 2, 3, 4, 5};
    vector<int> v2;
    v2.resize(v.size());
    replace(v.begin(), v.end(), 1, 99);
    replace_copy(v.begin(), v.end(), v2.begin(), 1, 99);
    
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;

    for_each(v2.begin(), v2.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 1, 2, 3, 4, 5};
    v.resize(v.size());

    replace_if(v.begin(), v.end(), [](int &a)
               { return a < 4; }, 99);

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });

    cout << endl;
#endif

#if 0
    vector<int> v = {1, 1, 2, 3, 4, 5};
    vector<int> v2;
    v2.resize(v.size());

    replace_copy_if(v.begin(), v.end(), v2.begin(), [](int &a)
               { return a < 4; }, 99);

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;

    for_each(v2.begin(), v2.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

// 移除性算法（不太好做通用化操作）
#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    remove(v.begin(), v.end(), 3);
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
    cout << v.size() << endl; // 不会修改size
#endif

#if 0
    vector<int> v = {1, 2, 2, 3, 3, 4, 5};
    // unique(v.begin(), v.end());

    // 用自己写的通用删除
    Remove(v, 3);

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
    cout << v.size() << endl; // 不会修改size
#endif

// 变序性算法
#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    reverse(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
    cout << v.size() << endl; // 不会修改size
#endif

#if 0
    // 旋转
    vector<int> v = {1, 2, 3, 4, 5};
    rotate(v.begin(), v.begin() + 3, v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
    cout << v.size() << endl; // 不会修改size
#endif

#if 0
    // 全排列：一个数列从小到大到从大到小的全部可能情况
    vector<int> v = {1, 2, 3, 4, 5};

    prev_permutation(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    // 随机洗牌
    vector<int> v = {1, 2, 3, 4, 5};
    srand(time(nullptr));
    // random_shuffle(v.begin(), v.end());
    RandomShuffle(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    // 不稳定
    // partition(v.begin(), v.end(), [](int a)
    //           { return a % 2 == 0; });

    // 稳定（快慢指针法）
    stable_partition(v.begin(), v.end(), [](int a)
              { return a % 2 == 0; });

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

// 排序性算法
#if 0
    // 不稳定的排序（堆排 快排）
    // size < 16 插排
    // size > 16 递归深度归0 堆排
    //           不为0 快排

    vector<int> v = {1, 2, 3, 4, 5};
    
    // 默认从小到大
    sort(v.begin(), v.end());
    // 从大到小
    // sort(v.begin(), v.end(), std::greater<int>());
  
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    // 稳定的排序（插排 归并）
    // size < 15 插排
    // size > 15 先分组插入再归并排序

    vector<int> v = {2, 1, 3, 4, 5};
    
    stable_sort(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {5, 1, 4, 2, 3};
    
    partial_sort(v.begin(), v.begin() + 2, v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {99, 8, 3, 1, 4, 2, 0};
    
    // 只排第n个元素
    nth_element(v.begin(), v.begin() + 1, v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {99, 8, 3, 1, 4, 2, 0};
    
    // 默认最大堆
    make_heap(v.begin(), v.end());
    // 最小堆（less最大堆）
    // make_heap(v.begin(), v.end(), std::greater<int>());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {99, 8, 3, 1, 4, 2, 0};

    // 先构建一个堆
    make_heap(v.begin(), v.end());
    // 再插入一个元素
    v.push_back(12);
    // 再重新构建堆
    push_heap(v.begin(), v.end());

    // 从堆里面弹出根，把根塞到后面去
    // pop_heap(v.begin(), v.end());

    // 排序
    sort_heap(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

// 已序区间算法
#if 0
    // 二分法
    vector<int> v = {1, 2, 3, 4, 5};

    cout << binary_search(v.begin(), v.end(), 99) << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    vector<int> v2 = {1, 2};
    
    cout<<includes(v.begin(), v.end(), v2.begin(), v2.end()) << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 4, 5};
    vector<int> v2 = {1, 2};
    
    // 大于等于
    cout << *lower_bound(v.begin(), v.end(), 2) << endl;
    // 大于
    cout << *upper_bound(v.begin(), v.end(), 2) << endl;
#endif

#if 0
    vector<int> v = {1, 2, 2, 2, 3, 4, 5};
    vector<int> v2 = {1, 2};

    auto pair = equal_range(v.begin(), v.end(), 2);
    cout << distance(pair.first, pair.second) << endl;
#endif

#if 0
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {2, 3, 4};
    vector<int> result;
    result.resize(v1.size() + v2.size());
    // 并集
    set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    // 交集
    set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    // 补集
    set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    // 补集的集合
    set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    for_each(result.begin(), result.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

#if 0
    vector<int> v = {1, 2, 3, 1, 2, 4};
    
    // 只发生在一个序列中的归并
    inplace_merge(v.begin(), v.begin() + 3, v.end());
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
#endif

    return 0;
}